package math;

import java.util.Stack;

public class ArithmeticExpression {

	Stack<Integer> stack;

	/*
	 * invalid expr: 1+(), (1+2)3, 1+01, (1+2 ...
	 */
	public boolean isValid(String expression) {
		String expr = '(' + expression + ')';
		stack = new Stack<Integer>();
		for (int i = 0; i < expr.length(); ++i) {
			int ch = expr.charAt(i);
			if (ch == ' ')
				continue;
			if (ch >= '0' && ch <= '9') {
				boolean flag = ch == '0';
				while (i + 1 < expr.length()
						&& Character.isDigit(expr.charAt(i + 1))
						&& i++ > Integer.MIN_VALUE) {
					if (flag)
						return false;
				}
				if (!stack.isEmpty()
						&& (stack.peek() == ')' || stack.peek() == -1))
					return false;
				stack.push(-1);
			} else {
				if ((ch == '+' || ch == '-' || ch == '*' || ch == '/')
						&& (stack.isEmpty() || (stack.peek() != -1 && stack
								.peek() != ')'))) {
					return false;
				} else if (ch == '(' && !stack.isEmpty()
						&& (stack.peek() == -1 || stack.peek() == ')')) {
					return false;
				} else if (ch == ')'
						&& (stack.isEmpty() || (stack.peek() != -1 && stack
								.peek() != ')'))) {
					return false;
				}
				stack.push(ch);
			}
			if (ch == ')') {
				stack.pop();
				while (!stack.isEmpty() && stack.pop() != '(')
					;
				if (stack.isEmpty() && i != expr.length() - 1) {
					return false;
				}
				stack.push(-1);
			}
		}
		return stack.isEmpty() || (stack.pop() == -1 && stack.isEmpty());
	}

	public int calculate(String expression) {
		String expr = '(' + expression + ')';
		stack = new Stack<Integer>();
		for (int i = expr.length() - 1; i >= 0; --i) {
			int ch = expr.charAt(i);
			if (ch == ' ')
				continue;
			if (ch >= '0' && ch <= '9') {
				int val = 0;
				int d = 1;
				do {
					val += d * (expr.charAt(i) - '0');
					d *= 10;
				} while (i - 1 >= 0 && Character.isDigit(expr.charAt(i - 1))
						&& i-- > Integer.MIN_VALUE);
				stack.push(val);
			} else {
				stack.push(ch);
			}
			if (ch == '(') {
				stack.pop();
				stack.push(compress(1));
			}
		}
		return stack.pop();
	}

	private int compress(int sym) {
		int val = stack.pop();
		int ch = stack.pop();
		while (ch != ')') {
			if (ch == '*') {
				val *= stack.pop();
			} else if (ch == '/') {
				val /= stack.pop();
			} else if (ch == '-') {
				return val * sym + compress(-1);
			} else {
				return val * sym + compress(1);
			}
			ch = stack.pop();
		}
		return val * sym;
	}

	public static void main(String[] args) {
		ArithmeticExpression a = new ArithmeticExpression();
		System.out.println(a.calculate("((101+(2)/2)+(2+5*2-1))"));
		System.out.println(a.calculate("(((((((1+2)+3)+4)+5)+6)+7)+8)"));
		System.out.println(a.calculate("12-10*11+6/3*4-7"));
		System.out.println(a
				.calculate("((2    *   4)-7*2+(5-(6   * 7)+   4 )   )"));
		System.out.println(a.isValid("((101+(2)/2)+(2+5*2-1))"));
		System.out.println(a.isValid("((1)+(2)+3"));
		System.out.println(a.isValid("(1+2)2"));
		System.out.println(a.isValid("(((((1+2)"));
	}
}
